#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
const int N = 2e5 + 5;

int n, m;
ll y, z, p;
ll fastpow(ll b, ll p, ll mod) {
  if (b % mod == 0) return 0;
  b %= mod;
  ll res = 1;
  while (p) {
    if (p & 1) res = res * b % mod;
    b = b * b % mod;
    p >>= 1;
  }
  return res;
}
void f1(ll y, ll z, ll p) { cout << fastpow(y, z, p) << endl; }
void f2(ll y, ll z, ll p) {
  y %= p, z %= p;
  if (!y && z) {
    cout << "Orz, I cannot find x!" << endl;
    return;
  }
  ll x = fastpow(y, p - 2, p) * z % p;
  cout << x << endl;
}
ll bsgs(ll b, ll a, ll p) {
  b %= p, a %= p;
  if (a == 1) return 0;
  if (!b && !a) return 1;
  if (!b && a) return -1;
  map<ll, ll> mp;
  ll k = ceil(sqrt(p));
  ll x = 1;
  rep(i, 0, k - 1) {
    mp[x * a % p] = i;
    x = x * b % p;
  }
  b = x, x = 1;
  rep(i, 1, k) {
    x = x * b % p;
    if (mp.count(x)) {
      return i * k - mp[x];
    }
  }
  return -1;
}
void f3(ll y, ll z, ll p) {
  ll x = bsgs(y, z, p);
  if (x < 0)
    cout << "Orz, I cannot find x!" << endl;
  else
    cout << x << endl;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t, k;
  cin >> t >> k;
  while (t--) {
    cin >> y >> z >> p;
    if (k == 1)
      f1(y, z, p);
    else if (k == 2)
      f2(y, z, p);
    else
      f3(y, z, p);
  }
  return 0;
}